#include"StringPool.h"
#include"variable.h"
#include<vector>
#include<string>
#include<fstream>
#include<ctime>
#include"Util.h"
#include"Parameters.h"
#include"DependencyInstance.h"
#include"KBestParseForest4OGTSibling.h"
#include"DependencyDecoder4OGTSibling.h"
#include"DependencyPipe4OGTSibling.h"
using namespace std;

DependencyDecoder4OGTSibling::DependencyDecoder4OGTSibling(DependencyPipe *pipe) : DependencyDecoder3O(pipe){}

DependencyDecoder4OGTSibling::~DependencyDecoder4OGTSibling(){}

double DependencyDecoder4OGTSibling::getGrandTriTripProb(int gpar, int par, int ch1, int ch2, int ch3, std::vector<vector<vector<vector<vector<double> > > > > &probs_gttrips){
	int ch1_fin, ch2_fin, ch3_fin;
	if(gpar < par){
		ch1_fin = ch1 - gpar - 1;
		if(ch1 < par){
			ch2_fin = ch2 - gpar - 1;
			ch3_fin = ch3 - gpar - 1;
		}
		else if(ch1 == par){
			ch2_fin = ch2 - gpar - 1;
			if(ch2 <= ch1){
				ch3_fin = ch3 - gpar - 1;
			}
			else{
				ch3_fin = ch3 - ch2 - 1;
			}
		}
		else{
			ch2_fin = ch2 - ch1 - 1;
			ch3_fin = ch3 - ch2 - 1;
		}
	}
	else{
		ch1_fin = ch1;
		if(ch1 < par){
			ch2_fin = ch2;
			ch3_fin = ch3;
		}
		else if(ch1 == par){
			ch2_fin = ch2;
			if(ch2 <= ch1){
				ch3_fin = ch3;
			}
			else{
				ch3_fin = ch3 - ch2 - 1;
			}
		}
		else{
			ch2_fin = ch2 - ch1 - 1;
			ch3_fin = ch3 - ch2 - 1;
		}
	}
	return probs_gttrips[gpar][par][ch1_fin][ch2_fin][ch3_fin];
}

vector<pair<FeatureVector*, string*> >* DependencyDecoder4OGTSibling::decodeProjective(DependencyInstance *inst, std::vector<vector<vector<double> > > &probs, std::vector<vector<vector<double> > > &probs_trips, std::vector<vector<vector<double> > > &probs_sibs, std::vector<vector<vector<double> > > &probs_grands, std::vector<vector<double> > &probs_gchs, std::vector<vector<vector<vector<double> > > > &probs_gtrips, std::vector<vector<vector<vector<double> > > > &probs_gsibs, std::vector<vector<vector<double> > > &probs_coords, std::vector<vector<vector<vector<double> > > > &probs_ttrips, std::vector<vector<vector<vector<double> > > > &probs_tsibs, std::vector<vector<vector<vector<vector<double> > > > > &probs_gttrips, std::vector<vector<vector<vector<double> > > > &nt_probs, int K, ParseForestItem *****GTSib_chart){
	vector<string*>* forms = inst->forms;

	int length = (int)(forms->size());
	vector<vector<int> >* static_types = NULL;
	if(pipe->labeled){
		static_types = this->getTypes(nt_probs, length);
	}

	KBestParseForest4OGTSibling pf = KBestParseForest4OGTSibling(GTSib_chart, 0, length - 1, *inst, K);

	bool added = false;
	bool added1 = false, added2 = false;
	bool coord = false;

	DependencyPipe4OGTSibling *pipe_g = (DependencyPipe4OGTSibling*)(pipe);

	for(int s = 0; s < length; s++){
		for(int g = 0; g < length; g++){
			pf.add(g, s, -1, 0, 0.0);
			pf.add(g, s, -1, 1, 0.0);
		}
	}

	for(int j = 1; j < length; j++){
		for(int s = 0; s < length && s + j < length; s++){
			int t = s + j;

			double prodProb_st = probs[s][t][0];
			double prodProb_ts = probs[s][t][1];

			int type1 = pipe->labeled ? (*static_types)[s][t] : 0;
			int type2 = pipe->labeled ? (*static_types)[t][s] : 0;

			double nt_prob_s_01 = 0.0;
			double nt_prob_s_10 = 0.0;
			double nt_prob_t_00 = 0.0;
			double nt_prob_t_11 = 0.0;
			
			
			if(pipe->labeled){
				nt_prob_s_01 = nt_probs[s][type1][0][1];
				nt_prob_s_10 = nt_probs[s][type2][1][0];
				nt_prob_t_00 = nt_probs[t][type1][0][0];
				nt_prob_t_11 = nt_probs[t][type2][1][1];
			}

			ParseForestItem *b1;
			ParseForestItem *c1;
			int length1;
			double prob_fin;
			vector<BestPair>* pairs;

			for(int g = 0; g < length; g++){
				if(g >= s && g <= t){
					continue;
				}
				for(int r = s; r < t; r++){
					// First case - create sibling
					b1 = pf.getItems(g, s, r, 0 ,1);
					c1 = pf.getItems(g, r + 1, t, 1, 1);

					pairs = pf.getKBestPairs(b1, c1);
					length1 = (int)(pairs->size());

					for(int k = 0; k < length1; k++){
						if(((*pairs)[k]).first == -1 || ((*pairs)[k]).second == -1){
							break;
						}

						int comp1 = (*pairs)[k].first;
						int comp2 = (*pairs)[k].second;
				
						double bc = b1[comp1].prob + c1[comp2].prob;

						added1 = pf.add(g, s, r, t, -1, 0, 2, bc, &(b1[comp1]), &(c1[comp2]));
						added2 = pf.add(g, s, r, t, -1, 1, 2, bc, &(b1[comp1]), &(c1[comp2]));
						if(!added1 && !added2){
							break;
						}
					}
					delete(pairs);
				}

				for(int m = s + 1; m < t; m++){
					int type1_m = pipe->labeled ? (*static_types)[s][m] : 0;
					int type2_m = pipe->labeled ? (*static_types)[t][m] : 0;
					//
					b1 = pf.getItems(s, s + 1, m, 1, 1);
					c1 = pf.getItems(s, m, t, 1, 2);

					pairs = pf.getKBestPairs(b1, c1);
					length1 = (int)(pairs->size());

					//gsssm
					double prob_sssm;
					prob_sssm = getTriTripProb(s, s, s, m, probs_ttrips, probs_tsibs);
					prob_sssm += probs_trips[s][s][m] + probs_sibs[s][m][0] + probs[s][m][0];

					double prob_gssm;
					prob_gssm = getGrandTripProb(g, s, s, m, probs_gtrips) + probs_gsibs[g][s][m][0];
					prob_gssm += probs_grands[g][s][m] + probs_gchs[g][m];

					double prob_gsssm;
					prob_gsssm = getGrandTriTripProb(g, s, s, s, m, probs_gttrips);
					prob_gsssm += prob_gssm + prob_sssm;


					//gssmt
					double prob_ssmt;
					prob_ssmt = getTriTripProb(s, s, m, t, probs_ttrips, probs_tsibs);
					prob_ssmt += probs_trips[s][m][t] + probs_sibs[m][t][1] + prodProb_st;

					double prob_gsmt;
					prob_gsmt = getGrandTripProb(g, s, m, t, probs_gtrips) + probs_gsibs[g][m][t][1];
					coord = pipe_g->isCoord(inst, s, m);
					if(coord){
						prob_gsmt += probs_coords[g][s][t];
					}
					prob_gsmt += probs_grands[g][s][t] + probs_gchs[g][t];

					double prob_gssmt;
					prob_gssmt = getGrandTriTripProb(g, s, s, m, t, probs_gttrips);
					prob_gssmt += prob_ssmt + prob_gsmt;

					for(int k = 0; k < length1; k++){
						if(((*pairs)[k]).first == -1 || ((*pairs)[k]).second == -1){
							break;
						}

						int comp1 = (*pairs)[k].first;
						int comp2 = (*pairs)[k].second;
				
						double bc = b1[comp1].prob + c1[comp2].prob;

						prob_fin = bc + prob_gsssm + prob_gssmt;

						if(pipe->labeled){
							prob_fin += nt_prob_s_01 + nt_prob_t_00;
						}

						added = pf.add_d(g, s, m, t, type1_m, 0, prob_fin, &(b1[comp1]), &(c1[comp2]));
						if(!added){
							break;
						}
					}
					delete(pairs);

					//
					b1 = pf.getItems(t, s, m, 0, 2);
					c1 = pf.getItems(t, m, t - 1, 0, 1);

					pairs = pf.getKBestPairs(b1, c1);
					length1 = (int)(pairs->size());

					//gtttm
					double prob_tttm;
					prob_tttm = getTriTripProb(t, t, t, m, probs_ttrips, probs_tsibs);
					prob_tttm += probs_trips[t][t][m] + probs_sibs[t][m][0] + probs[m][t][1];

					double prob_gttm;
					prob_gttm = getGrandTripProb(g, t, t, m, probs_gtrips) + probs_gsibs[g][t][m][0];
					prob_gttm += probs_grands[g][t][m] + probs_gchs[g][m];

					double prob_gtttm;
					prob_gtttm = getGrandTriTripProb(g, t, t, t, m, probs_gttrips);
					prob_gtttm += prob_gttm + prob_tttm;

					//gttms
					double prob_ttms;
					prob_ttms = getTriTripProb(t, t, m, s, probs_ttrips, probs_tsibs);
					prob_ttms += probs_trips[t][m][s] + probs_sibs[m][s][1] + prodProb_ts;

					double prob_gtms;
					prob_gtms = getGrandTripProb(g, t, m, s, probs_gtrips) + probs_gsibs[g][m][s][1];
					coord = pipe_g->isCoord(inst, t, m);
					if(coord){
						prob_gtms += probs_coords[g][t][s];
					}
					prob_gtms += probs_grands[g][t][s] + probs_gchs[g][s];

					double prob_gttms;
					prob_gttms = getGrandTriTripProb(g, t, t, m, s, probs_gttrips);
					prob_gttms += prob_gtms + prob_ttms;

					for(int k = 0; k < length1; k++){
						if(((*pairs)[k]).first == -1 || ((*pairs)[k]).second == -1){
							break;
						}

						int comp1 = (*pairs)[k].first;
						int comp2 = (*pairs)[k].second;
				
						double bc = b1[comp1].prob + c1[comp2].prob;

						prob_fin = bc + prob_gtttm + prob_gttms;

						if(pipe->labeled){
							prob_fin += nt_prob_t_11 + nt_prob_s_10;
						}

						added = pf.add_d(g, s, m, t, type2_m, 1, prob_fin, &(b1[comp1]), &(c1[comp2]));
						if(!added){
							break;
						}
					}
					delete(pairs);

					for(int r = s + 1; r < m; r++){
						b1 = pf.getItems_d(g, s, r, m, 0);
						c1 = pf.getItems(s, m, t, 0, 2);

						pairs = pf.getKBestPairs(b1, c1);
						length1 = (int)(pairs->size());

						double prob_srmt;
						prob_srmt = getTriTripProb(s, r, m, t, probs_ttrips, probs_tsibs);
						prob_srmt += probs_trips[s][m][t] + probs_sibs[m][t][1] + prodProb_st;

						double prob_gsrmt;
						prob_gsrmt = getGrandTriTripProb(g, s, r, m, t, probs_gttrips);
						prob_gsrmt += prob_gsmt + prob_srmt;

						for(int k = 0; k < length1; k++){
							if(((*pairs)[k]).first == -1 || ((*pairs)[k]).second == -1){
								break;
							}

							int comp1 = (*pairs)[k].first;
							int comp2 = (*pairs)[k].second;
				
							double bc = b1[comp1].prob + c1[comp2].prob;

							prob_fin = bc + prob_gsrmt;

							if(pipe->labeled){
								prob_fin += nt_prob_s_01 + nt_prob_t_00;
							}

							added = pf.add_d(g, s, m, t, type1_m, 0, prob_fin, &(b1[comp1]), &(c1[comp2]));
							if(!added){
								break;
							}
						}
						delete(pairs);
					}
					for(int r = m + 1; r < t; r++){
						b1 = pf.getItems(t, s, m ,1, 2);
						c1 = pf.getItems_d(g, m, r, t, 1);

						pairs = pf.getKBestPairs(b1, c1);
						length1 = (int)(pairs->size());

						double prob_trms;
						prob_trms = getTriTripProb(t, r, m, s, probs_ttrips, probs_tsibs);
						prob_trms += probs_trips[t][m][s] + probs_sibs[m][s][1] + prodProb_ts;

						double prob_gtrms;
						prob_gtrms = getGrandTriTripProb(g, t, r, m, s, probs_gttrips);
						prob_gtrms += prob_gtms + prob_trms;

						for(int k = 0; k < length1; k++){
							if(((*pairs)[k]).first == -1 || ((*pairs)[k]).second == -1){
								break;
							}

							int comp1 = (*pairs)[k].first;
							int comp2 = (*pairs)[k].second;
				
							double bc = b1[comp1].prob + c1[comp2].prob;

							prob_fin = bc + prob_gtrms;

							if(pipe->labeled){
								prob_fin += nt_prob_t_11 + nt_prob_s_10;
							}

							added = pf.add_d(g, s, m, t, type2_m, 1, prob_fin, &(b1[comp1]), &(c1[comp2]));
							if(!added){
								break;
							}
						}
						delete(pairs);
					}
				}

				b1 = pf.getItems(g, s, s, 0 ,1);
				c1 = pf.getItems(s, s + 1, t, 1, 1);

				pairs = pf.getKBestPairs(b1, c1);
				length1 = (int)(pairs->size());

				double prob_ssst;
				prob_ssst = getTriTripProb(s, s, s, t, probs_ttrips, probs_tsibs);
				prob_ssst += probs_trips[s][s][t] + probs_sibs[s][t][0] + prodProb_st;

				double prob_gsst;
				prob_gsst = getGrandTripProb(g, s, s, t, probs_gtrips) + probs_gsibs[g][s][t][0];
				prob_gsst += probs_grands[g][s][t] + probs_gchs[g][t];

				double prob_gssst;
				prob_gssst = getGrandTriTripProb(g, s, s, s, t, probs_gttrips);
				prob_gssst += prob_gsst + prob_ssst;

				for(int k = 0; k < length1; k++){
					if(((*pairs)[k]).first == -1 || ((*pairs)[k]).second == -1){
						break;
					}

					int comp1 = (*pairs)[k].first;
					int comp2 = (*pairs)[k].second;


					double bc = b1[comp1].prob + c1[comp2].prob;

					prob_fin = bc + prob_gssst;

					if(pipe->labeled){
						prob_fin += nt_prob_s_01 + nt_prob_t_00;
					}

					added = pf.add(g, s, s, t, type1, 0, 0, prob_fin,  &(b1[comp1]), &(c1[comp2]));
					if(!added){
						break;
					}
				}
				delete(pairs);

				b1 = pf.getItems(t, s, t - 1, 0, 1);
				c1 = pf.getItems(g, t, t, 1, 1);

				pairs = pf.getKBestPairs(b1, c1);
				length1 = (int)(pairs->size());

				double prob_ttts;
				prob_ttts = getTriTripProb(t, t, t, s, probs_ttrips, probs_tsibs);
				prob_ttts += probs_trips[t][t][s] + probs_sibs[t][s][0] + prodProb_ts;

				double prob_gtts;
				prob_gtts = getGrandTripProb(g, t, t, s, probs_gtrips) + probs_gsibs[g][t][s][0];
				prob_gtts += probs_grands[g][t][s] + probs_gchs[g][s];

				double prob_gttts;
				prob_gttts = getGrandTriTripProb(g, t, t, t, s, probs_gttrips);
				prob_gttts += prob_gtts + prob_ttts;

				for(int k = 0; k < length1; k++){
					if(((*pairs)[k]).first == -1 || ((*pairs)[k]).second == -1){
						break;
					}

					int comp1 = (*pairs)[k].first;
					int comp2 = (*pairs)[k].second;
				
					double bc = b1[comp1].prob + c1[comp2].prob;

					prob_fin = bc + prob_gttts;

					if(pipe->labeled){
						prob_fin += nt_prob_t_11 + nt_prob_s_10;
					}
					added = pf.add(g, s, t, t, type2, 1, 0, prob_fin, &(b1[comp1]), &(c1[comp2]));
					if(!added){
						break;
					}
				}
				delete(pairs);

				for(int r = s + 1; r < t; r++){
					b1 = pf.getItems_d(g, s, r, t, 0);
					c1 = pf.getItems(s, t, t, 0, 1);

					pairs = pf.getKBestPairs(b1, c1);
					length1 = (int)(pairs->size());

					for(int k = 0; k < length1; k++){
						if(((*pairs)[k]).first == -1 || ((*pairs)[k]).second == -1){
							break;
						}

						int comp1 = (*pairs)[k].first;
						int comp2 = (*pairs)[k].second;
				
						double bc = b1[comp1].prob + c1[comp2].prob;

						added = pf.add(g, s, r, t, type1, 0, 0, bc, &(b1[comp1]), &(c1[comp2]));
						if(!added){
							break;
						}
					}
					delete(pairs);

					b1 = pf.getItems(t, s, s, 1, 1);
					c1 = pf.getItems_d(g, s, r, t, 1);

					pairs = pf.getKBestPairs(b1, c1);
					length1 = (int)(pairs->size());

					for(int k = 0; k < length1; k++){
						if(((*pairs)[k]).first == -1 || ((*pairs)[k]).second == -1){
							break;
						}

						int comp1 = (*pairs)[k].first;
						int comp2 = (*pairs)[k].second;
				
						double bc = b1[comp1].prob + c1[comp2].prob;

						added = pf.add(g, s, r, t, type2, 1, 0, bc, &(b1[comp1]), &(c1[comp2]));
						if(!added){
							break;
						}
					}
					delete(pairs);
				}

				for(int r = s; r <= t; r++){
					if(r != s){
						b1 = pf.getItems(g, s, r, 0, 0);
						c1 = pf.getItems(s, r, t, 0, 1);
						pairs = pf.getKBestPairs(b1, c1);
						length1 = (int)(pairs->size());

						for(int k = 0; k < length1; k++){
							if(((*pairs)[k]).first == -1 || ((*pairs)[k]).second == -1){
								break;
							}

							int comp1 = (*pairs)[k].first;
							int comp2 = (*pairs)[k].second;

							double bc = b1[comp1].prob + c1[comp2].prob;
							added = pf.add(g, s, r, t, -1, 0, 1, bc, &(b1[comp1]), &(c1[comp2]));
							if(!added){
								break;
							}
						}
						delete(pairs);
					}

					if(r != t){
						b1 = pf.getItems(t, s, r, 1, 1);
						c1 = pf.getItems(g, r, t, 1, 0);
						pairs = pf.getKBestPairs(b1, c1);
						length1 = (int)(pairs->size());
						for(int k = 0; k < length1; k++){
							if(((*pairs)[k]).first == -1 || ((*pairs)[k]).second == -1){
								break;
							}

							int comp1 = (*pairs)[k].first;
							int comp2 = (*pairs)[k].second;

							double bc = b1[comp1].prob + c1[comp2].prob;
							added = pf.add(g, s, r, t, -1, 1, 1, bc, &(b1[comp1]), &(c1[comp2]));
							if(!added){
								break;
							}
						}
						delete(pairs);
					}
				}
			}
		}
	}
	if(static_types != NULL){
		delete(static_types);
	}

	bool normal = (pipe->options->root_type == 0);
	vector<pair<FeatureVector*, string*> >* result = NULL;
	result = pf.getBestParses(inst, pipe, probs, probs_trips, probs_sibs, probs_ttrips, probs_tsibs, nt_probs, pipe->labeled, normal);
	return result;
}